package Offer.offer2016;


public class Test08 
{

	public static void main(String[] args) 
	{
        int[]array={1,2,3};
//        System.out.println(findMin(array));
        RotateArrayMinValue test = new RotateArrayMinValue();
        System.out.println(test.getMinFromArray(array));
	}
	public static int findMin(int[] array)
	{	
		if(array==null || array.length==0)
			return 0;
		if(array[0]<array[array.length-1])
		{
			return array[0];
		}
		int i = 0;
		int j = array.length-1;
		int mid=(i+j)/2;					
		if(array[0]==array[array.length-1]&&array[0]==array[mid])
		{
		     return orderFingMin(array);
		}
		while(array[i]>=array[j])
		{
			if(j-i==1)
			{
				return array[j];
			}
			if(array[mid]>=array[i])
			{
				i=mid;
			}
			if(array[mid]<=array[j])
			{
				j=mid;
			}
			mid=(i+j)/2;
		}			    			
		return array[j];
		
	}
	public static int orderFingMin(int[] array)
	{
		int min=array[0];		
		for(int i=1;i<=array.length-1;i++)
		{
			if(array[i]<min)
			{
				min=array[i];
			}
		}
		return min;
	}

}

class RotateArrayMinValue{
	public int getMinFromArray(int []arr){
		if(arr == null || arr.length <=0 ){
			throw new RuntimeException("������û��ֵ ");
		}
		int start = 0;
		int middle = start;
		int end = arr.length - 1;
		while(arr[start] >= arr[end]){
			if(end - start == 1){
				middle = end;
				break;
			}
			middle = (start + end) / 2;
			if(arr[middle] > arr[start]){
				start = middle;
			}else if(arr[middle] < arr[end]){
				end = middle;
			}else if(arr[middle] == arr[start] && arr[middle] == arr[end]){
				return orderFingMin(arr, start,end);
			}
		}
		return arr[middle];
	}
	public static int orderFingMin(int[] array, int start,int end){
		int min=array[start];		
		for(int i=start;i<=end;i++){
			if(array[i]<min){
				min=array[i];
			}
		}
		return min;
	}
}


//��  ����ת�����л�ȡ��Сֵ{
//	���� ���� ����ת�����ȡ��Сֵ ������ �������飩{
//		
//		����  ��Ч��
//	}
//}
